/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.distributions;

import java.util.ArrayList;
import java.util.HashMap;

import mosdi.util.Distributions;

// NOTE: Implementation by FFT does not work due to numerical reasons. Small values
//       ca. <1e-16 do not come out of iFFT, but those are the interesting ones.

/** Class that can fastly compute the n-fold convolution of a 
 *  distribution given at construction time. */
public class LazyDistributionConvolver implements DistributionConvolver {

	ArrayList<double[]> powerOfTwoFoldDistributions;
	HashMap<Integer,double[]> distributionCache;
	HashMap<Integer,double[]> ccdfCache;
	
	/** Constructor. All requests are cached.
	 *  @param distribution Distribution that is to be self-convolved.
	 */
	public LazyDistributionConvolver(double[] distribution) {
		this(distribution, true);
	}

	public LazyDistributionConvolver(double[] distribution, boolean cacheOn) {
		powerOfTwoFoldDistributions = new ArrayList<double[]>();
		powerOfTwoFoldDistributions.add(distribution);
		if (cacheOn) {
			distributionCache = new HashMap<Integer,double[]>();
			distributionCache.put(1, distribution);
			ccdfCache = new HashMap<Integer,double[]>();
		}
	}

	private double[] getPowerOfTwoDistributions(int exponent) {
		for (int i=powerOfTwoFoldDistributions.size(); i<=exponent; ++i) {
			double[] a = powerOfTwoFoldDistributions.get(i-1);
			double[] b = Distributions.convolve(a,a);
			powerOfTwoFoldDistributions.add(b);
			int n = 1<<i;
			distributionCache.put(n, b);
		}
		return powerOfTwoFoldDistributions.get(exponent);
	}
	
	public double[] getDistribution(int selfConvolution) {
		double[] result = null;
		if (distributionCache!=null) {
			result = distributionCache.get(selfConvolution);
			if (result!=null) return result;
		}
		int e = 0;
		int i = selfConvolution;
		while (i>0) {
			if (i%2==1) {
				if (result==null) result = getPowerOfTwoDistributions(e);
				else result = Distributions.convolve(result,getPowerOfTwoDistributions(e));
			}
			i = i>>1;
			e+=1;
		}
		if (distributionCache!=null) {
			distributionCache.put(selfConvolution, result);
		}
		return result;
	}
	
	/** Returns the (right) cumulative distribution function, i.e. result[0]==1. */
	public double[] getCCDF(int selfConvolution) {
		double[] result = null; 
		if (ccdfCache!=null) {
			result = ccdfCache.get(selfConvolution);
		}
		if (result==null) {
			result = Distributions.toCCDF(getDistribution(selfConvolution));
			if (ccdfCache!=null) {
				ccdfCache.put(selfConvolution, result);
			}
		}
		return result;
	}
	
	/** If D is the underlying distribution (given on construction time),
	 *  then D^{*selfConvolution}(>=value) is returned. */
	public double getPValue(int selfConvolution, int value) {
		double[] cdf = getCCDF(selfConvolution);
		if (value>=cdf.length) return 0.0;
		return cdf[value];
	}
}
